#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/*
图的邻接矩阵表示法
*/

#define MAX_VERTEX_NUM 50 // 最大顶点数

// 邻接矩阵表示的存储结构
typedef struct adjmatrix
{
    char vexs[MAX_VERTEX_NUM];                // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
} MGraph;

// 创建无向图，采用压缩主对角线
void createMGraph(MGraph *G, int n, int e)
{
    // 读入顶点数和边数
    scanf("%d, %d", &n, &e);
    // 初始化顶点数组
    for (int i = 0; i < n; i++)
    {
        scanf("%c ", &G->vexs[i]);
    }

    int i, j;
    // 初始化邻接矩阵元素为无穷大
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            G->arcs[i][j] = INT_MAX;
        }
    }

    int w;
    // 读入e条边，建立邻接矩阵
    for (int k = 0; k < e; k++)
    {
        // 读入一条边的两端顶点序号 i、j 及 边上的权 w
        scanf("%d, %d, %d", &i, &j, &w);
        G->arcs[i][j] = w;
        G->arcs[j][i] = w;
    }
}

// DFS  深度优先搜索遍历
int visited[20];
void DFS(MGraph G, int i, int n){

    printf("v%d-->", i);
    visited[i] = 1;
    // 标记 vi 已访问过
    for (int j = 0; j < n; j++)
    {
        // 未被访问过则递归调用
        if(G.arcs[i][j] == 1 && !visited[j]){
            DFS(G, j, n);
        }
    }
    
}

// BFS  广度优先搜索遍历
void BFS(MGraph G, int i, int n){
    // 通过队列实现
}

// Dijkstra  算法

int main()
{
    return 0;
}